import java.util.Arrays;
import java.util.Comparator;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/7/1
 * \* Time: 22:21
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 俄罗斯套娃信封问题 {
    public int maxEnvelopes(int[][] envelopes) {
        int n=envelopes.length;
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                //按宽度升序排列，如果宽度一样则按高度降序排列
                return a[0]==b[0]?b[1]-a[1]:a[0]-b[0];
            }
        });

        //对高度数组寻早LIS
        int[] height=new int[n];
        for(int i=0;i<n;i++){
            height[i]=envelopes[i][1];
        }

        return lengthOfLIS(height);
    }

    public int lengthOfLIS(int[] nums) {
        int[] dp=new int[nums.length];
        //base case:dp数组全部初始化为1
        Arrays.fill(dp,1);
        //记录结果
        int res=0;
        for(int i=0;i< nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            //每轮结束更新结果
            if(dp[i]>res){
                res=dp[i];
            }
        }

        return res;
    }
}